// 图-邻接表
#ifndef ADJ_LIST_H
#define ADJ_LIST_H

#define MAX_VEX 100

typedef char VertexType;

// 边表结点
typedef struct EdgeNode
{
	int adjVex;			   // 表示该顶点对应下标
	int weight;			   // 边的权值
	struct EdgeNode *next; // 指向下一个邻接点
} EdgeNode;

// 顶点表结点
typedef struct VertexNode
{
	VertexType data;	 // 顶点中的数据
	EdgeNode *firstNode; // 指向的第一个结点
} VertexNode;

// 邻接表定义
typedef struct
{
	VertexNode vertex[MAX_VEX]; // 所有顶点
	int vertexNum, edgeNum;		// 顶点数和边数
} AdListGraph;

/**
 * 初始化一个邻接表
 * @param adList 传入空的邻接表引用以初始化
 */
void createAdList(AdListGraph &);

/**
 * 查找对应顶点的索引
 * @param u 传入顶点值
 * @return 返回该值顶点的索引，不存在返回-1
 */
int locateAdVex(AdListGraph &, VertexType);

/**
 * 判断v和w是否直接相连
 * @param adList 传入邻接表引用
 * @param v 传入v的索引
 * @param w 传入w的索引
 * @return v与w连通返回1，否则返回0
 */
int isAdConnected(AdListGraph &, int, int);

/**
 * 返回某个点的第一个邻接点的索引
 * @param adList 传入邻接表引用
 * @param v 传入顶点索引
 * @return 返回传入点的第一个邻接点，找不到则返回-1
 */
int firstAdjListVex(AdListGraph &, int);

/**
 * 查找v相对于w的下一个邻接点
 * @param adList 传入邻接表引用
 * @param v 传入顶点索引
 * @param w 传入邻接点索引
 * @return 返回v相对于w的下一个邻接点，若w是v的最后一个邻接点，则返回-1
 */
int nextAdjListVex(AdListGraph &, int, int);

/**
 * 插入一个顶点
 * @param adList 传入邻接表引用
 * @param u 传入插入顶点的值
 */
void insertAdVex(AdListGraph &, VertexType);

/**
 * 插入一条弧
 * @param adList 待操作的邻接表
 * @param v 待连接的起点顶点索引
 * @param w 待连接的终点顶点索引
 * @param weight 权值
 */
void insertAdArc(AdListGraph &, int, int, int);

/**
 * 深度优先遍历-递归逻辑部分
 * @param adList 遍历的邻接表
 * @param i 开始遍历的顶点的索引
 * @param visited 访问辅助数组，标识哪些点被访问
 * @param visit 遍历回调函数
 */
void DFS(AdListGraph &, int, int *, void(VertexType &));

/**
 * 深度优先遍历-起始部分
 * @param adList 遍历的邻接表
 * @param visit 遍历回调函数
 */
void DFSTraverse(AdListGraph &, void(VertexType &));

/**
 * 广度优先遍历
 * @param adList 遍历的邻接表
 * @param visit 遍历回调函数
 */
void BFSTraverse(AdListGraph &, void(VertexType &));

/**
 * 输出邻接表
 * @param adList 待输出的邻接表引用
 */
void printAdList(AdListGraph &);

#include "./adj-list.cpp"

#endif